class Solution:
    def restoreIpAddresses(self, s):
        ans = []
        path = []

        def is_valid(s):
            if s == "":
                return False
            
            if len(s) > 3:
                return False
            
            if s == "0":
                return True
            
            if s[0] == "0":
                return False
            
            return 0 < int(s) <= 255

        def dfs(s, start):
            if len(path) == 3:
                postfix = s[start:]
                if not is_valid(postfix):
                    return 
                
                path.append(postfix)
                ans.append(".".join(path))
                path.pop()
                return
            
            for i in range(1,4):
                temp = s[start:start + i]
                if not is_valid(temp):
                    continue
                path.append(temp)
                dfs(s, start+i)
                path.pop()
        
        dfs(s, 0)
        return ans

if __name__ == '__main__':
    s = Solution()
    ans = s.restoreIpAddresses("101023")
    print(ans)
        


            

            


